Intuition

문제링크: https://leetcode.com/problems/sum-of-k-mirror-numbers/

이 문제는 10진법과 k진법 모두에서 팰린드롬인 수 중 앞에서부터 n개를 찾아 그 합을 구하는 문제입니다.

처음에는 다음과 같이 접근했습니다:

팰린드롬인지 확인하는 함수 작성 (check_k)
10진수를 k진법 문자열로 바꾸는 함수 작성 (num_to_base)
1부터 순차적으로 수를 증가시키며 두 조건을 만족하는 수를 찾아 누적

하지만 n이 커지고 k가 클수록 모든 수를 순회하는 방식은 시간초과가 발생했습니다.

Approach

🔹 초기 접근 (시간초과 발생)

def check_k(s: str) -> bool:
    return s == s[::-1]

def num_to_base(num: int, base: int) -> str:
    result = ""
    while num > 0:
        result = str(num % base) + result
        num //= base
    return result or "0"

class Solution:
    def kMirror(self, k: int, n: int) -> int:
        cnt = 0
        res_sum = 0
        i = 1
        while cnt < n:
            if check_k(str(i)) and check_k(num_to_base(i, k)):
                res_sum += i
                cnt += 1
            i += 1
        return res_sum

문제점: 팰린드롬이 아닌 수까지 전부 확인 → 비효율

🔹 개선 접근: 팰린드롬 수만 생성하기

불필요한 숫자를 확인하지 않도록, 10진수 팰린드롬 숫자만 생성해서 탐색 대상으로 삼았습니다.

팰린드롬은 앞 절반만 만들고 뒤를 반전시켜 붙이면 효율적으로 생성할 수 있습니다.

def generate_all_palindromes():
    length = 1
    while True:
        half_start = 10 ** ((length - 1) // 2)
        half_end = 10 ** ((length + 1) // 2)
        for half in range(half_start, half_end):
            s = str(half)
            if length % 2 == 0:
                yield int(s + s[::-1])
            else:
                yield int(s + s[-2::-1])
        length += 1

이제 작은 수부터 팰린드롬만 생성하면서 k진수에서도 팰린드롬인지 체크하면 훨씬 빠릅니다.

Code (최종 구현)

def check_k(s: str) -> bool:
    return s == s[::-1]

def num_to_base(num: int, base: int) -> str:
    result = ""
    while num > 0:
        result = str(num % base) + result
        num //= base
    return result or "0"

def generate_all_palindromes():
    length = 1
    while True:
        half_start = 10 ** ((length - 1) // 2)
        half_end = 10 ** ((length + 1) // 2)
        for half in range(half_start, half_end):
            s = str(half)
            if length % 2 == 0:
                yield int(s + s[::-1])
            else:
                yield int(s + s[-2::-1])
        length += 1

class Solution:
    def kMirror(self, k: int, n: int) -> int:
        cnt = 0
        res_sum = 0
        for num in generate_all_palindromes():
            if check_k(num_to_base(num, k)):
                res_sum += num
                cnt += 1
                if cnt == n:
                    break
        return res_sum

Complexity

Time complexity: 매우 최적화되었지만 정확한 상한은 정의하기 어려움. (팰린드롬 수 생성 + 진법 변환 + 문자열 비교 포함)
Space complexity: $O(1)$ (고정된 변수들만 사용)

Note

진법 변환할 때 num_to_base()는 가장 기본적이고 직접 구현하기 쉬운 방식
브루트포스 대신 문제의 성질(팰린드롬의 구조)을 이용한 생성 방식이 효과적